前言

大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
那就開始今天的解題吧~

Question

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

Constraints:

• 1 <= s.length <= 10^5
• s consists of only uppercase English letters.
• 0 <= k <= s.length

Think

給一個字串s與一個k值，k代表總共有幾個字元可以被替換掉，而s中只會出現大寫的字母(A-Z)，要回傳s中被替換掉k個字元後，同一個字母重複出現的最長的長度。

• 用兩個index(left, right)，主要是由right移動
• 直到right-left+1-dictionary中出現最多次的字母 > k，也就是需要替換的字母數量超過我們可替換的，我們才移動left~
  • 右移left1格的同時，我們把dictionary中s[left]的數量扣1
• 然後每次比較看看我們的最大值有沒有超過原先的~

在CSDN上看到作者： 负雪明烛做的動圖，覺得很方便理解~

Code

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count_dict = {}
        
        left = 0
        right = 0
        
        result = 0
        
        while right < len(s):
            # print("Right Now: ", right)
            count_dict[s[right]] = 1 + count_dict.get(s[right], 0)
            
            if (right - left + 1) - max(count_dict.values()) > k:
                count_dict[s[left]] -= 1
                left += 1
            
            result = max((right - left + 1), result)
            right += 1
            # print("Per result: ", result)
        # print("\nFinal result: ", result)   
        
        return result

Submission

• 之前用dictionary call值都用dict_name[key]，但這樣每次都要另外加個if-else，判斷一下dictionary中有沒有這個key
  • 查了才發現有dict_name.get(key, default_value)這個方法，當dictionary中查不到這個key時，會回傳default_value給的數，這樣就不用再另外用if-else判斷是要給初始值還是加一了~

今天就到這邊啦~
大家明天見